B BIBLIOGRAPHIC DATA SHEET 1. Report No. MAC TM-35 3. Recipient's Accession No. 4. Title and Subtitle An Interactive Implementation of the Todd-Coxeter Algorithm 5. Report Date . Issued December 1973 7. Author(s) Richard J, Bonneau 8- Performing Organization Rept. MAC TM-3.5 9. Performing Organization Name and Address PROJECT MAC; MASSACHUSETTS INSTITUTE OF TECHNOLOGY : 545 Technology Square, Cambridge, Massachusetts 0213 9 10. Project/Task/Work Unit No. 11. Contract/Grant No. N00014-70-A-0362-0006 12. Sponsoring Organization Name and Address Office of Naval Research Department of the Navy Information Systems Program Arlington. Va 22217 13. Type of Report & Period Covered: Interim Scientific Report 14. 15. Supplementary Notes 16. Abstracts The Todd-Coxeter algorithm provides a systematic approach to the enumeration of cosets of a finitely presented group. This memo describes an interactive implementation of algorithm, including a manual on its use, examples, and methods of accessing the program. Applications of this algorithm are also discussed. 17. Key Words and Document Analysis. 17a. Descriptors Group Theory Symbol Manipulation 17b. Identifiers/Open-Ended Terms 17c COSATI Field/Group 18. Availability Statement Unlimited Distribution Write Project MAC Publications 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 26 22. Price FORM NT1S-35 (REV, 3-72) THIS FORM MAY BE REPRODUCED USCOMM-DC ^ 4 952- P 72 INSTRUCTIONS FOR COMPLETING FORM NTIS-35 (10-70) (Bibliographic Data Sheet based on COSATI Guidelines to Format Standards for Scientific and Technical Reports Prepared by or for the Federal Government, PB-180 600). 1. Report Number. Each individually bound report shall carry a unique alphanumeric designation selected by the performing organization or provided by the sponsoring organization. Use uppercase letters and Arabic numerals only. Examples FASEB-NS-87 and FAA-RD-68-09. 2. Leave blank. 3. Recipient's Accession Number. Reserved for use by each report recipient. / 4. Title and Subtitle. Title should indicate clearly and briefly the subject coverage of the report, and be displayed promi- nently. Set subtitle^ if used, in smaller type or otherwise subordinate it to orain title. When a report is prepared in more than one volume, repeat the primary title, add volume number and include suDtitle for the specific volume. 5- Report Date. Fach report sKall carry a date indicating at least month anVyear. Indicate the basis on which it was selected (e.g., date of issue, date of approval, date of preparation. 6. Performing Organization Code. Le^ye blank. 7. Author(s). Give name(s) in conventional order (e.g., John R.^oe, or J.Robert Doe). List author's affiliation if it differs from the performing organization. \ 8- Performing Organization Report Number. Insert if performyfg organization wishes to assign this number. 9- Performing Organization Name and Address. Giv\namtff street, city, state, and zip code. List no more than two levels of an organizational hierarchy. Display the name of t^eyfcrganizat ion exactly as it should appear in Government indexes such as USGRDR-I. 10. Project/Task/Work Unit Number. Use the projecyf task a^ntd work unit numbers under which the report was prepared. / \ 11. Contract/Grant Number. Insert contract or grajft number unde^ which report was prepared. 12. Sponsoring Agency Name and Address. Inclride zip code \ \ 13. Type of Report and Period Covered. Indicate interim, final, etc., aV , if applicable, dates covered \ 14. Sponsoring Agency Code. Leave blank. \ 15. Supplementary Notes. Enter information not included elsewhere but useful, such as: Prepared in cooperation with . . . Translation of . . . Presented at conference of . . . To be published in . . .\ Supersedes . . . Supplements . . . 16. Abstract. Include a brief (200 words or less) factual summary of the most significant information contained in the report. If the report contains a significant bibliography or literature survey, mention it hefce- 17. Key Words and Document Analysis, (a). Descriptors. Select from the Thesaurus of h.ngineering and Scientific Terms the proper authorized terms that identify the major concept of the research and are sufficiently specific and precise to be used as index entries for cataloging. \ (b). Identifiers and Open-Ended Terms. Use identifiers for project names, code names, equipment designators, etc. Use open-ended terms written in descriptor form for those subjects for which no descriptor exists. (c). COSATI Field/Group. Field and Group assignments are to be taken from the 1965 COSATI Subject Category List. Since the majority of documents are mukidisciplinary in nature, the primary Field/Group assignment(s) will be the specific discipline, area of human endeavor, or type of physical object. The application(s) will be cross-referenced with secondary Field/Group assignments that will follow the primary posting(s). 18. Distribution Stotement. Denote releasability to the public or limitat ion for reasons other than security for example "Re- lease unlimited**. Cite any availability to the public, with address and price. 19 & 20. Security Classification. Do not submit classified reports to the National Technical 21. Number of Pages. Insert the total number of pages, including this one and unnumbered pages, but excluding distribution list, if any. 22. Price. Insert the price set by the National Technical Information Service or the Government Printing Office, if known. FORM NTIS-35 (REV 3-72) USCOMM-DC 14952-P72 MAC TECHNICAL MEMORANDUM 35 AN INTERACTIVE IMPLEMENTATION OF THE TODD-COXETER ALGORITHM Richard J. Bonneau December 1973 This research was supported in part by the Raytheon Advanced Degree Program and by the Advanced Research Projects Agency of the Department of Defense under ARPA Order No. 2095 which was monitored by ONR Contract No. N00014- 70-A-0362-0006. MASSACHUSETTS INSTITUTE OF TECHNOLOGY PROJECT MAC CAMBRIDGE MASSACHUSETTS 02139 An Interactive Implementation of the Todci-Coxeter Algorithm Abstract The Todd-Coxeter algorithm provides a systematic approach to the enumeration of cosets of a finitely presented group. This memo describes an interactive implementation of algorithm, including a manual on its use, examples, and methods of accessing the program. Applications of this algorithm are also discussed. TABLE OF CONTENTS 1 . Introduction 3 2. User's Manual for the Todd-Coxeter Algorithm 4 3. Sample Session Number 1 8 4 . Disk Files for Input and/or Output 10 5 . Sample Session Number 2 11 6. Sample Session Number 3 17 7 . Miscellaneous Information 22 8. Getting onto the MATHLAB Computer 23 Bibliography 24 -3- 1. Introduction This memo presents a user's manual for the operation of an interactive version of the Todd-Coxeter algorithm for the computation of the index of a subgroup with respect, to a given group. The bulk of the FORTRAN program was derived from the program written by Cannon, et. al [1], but has been re-organized to provide for interactive use. The Todd-Coxeter Algorithm, as described in [2], [3] and [4], provides an efficient method for determining the order of a finite group which is described in terms of generators and relations. The algorithm also can be used to compute the index of any subgroup provided the subgroup is presented by generators which are words in the generators of the group. This algorithm has been used widely by group theorists and mathematicians for a number of applications. These applications include construction of a presentation of a known group by generators and relations [5], computation of part of the Schur multiplier of a small finite Lie group (PSU(3,4)) [5], calculating double cosets H x K given the single coset table form of the sub- groups H and K [6], and determination of a set of coset representatives for a subgroup [6]. The Todd-Coxeter algorithm has been acknowledged as a power- ful and necessary tool for any automated group theory project. The current program is written in the FORTRAN IV programming language and runs under a simulated PDP-10/50 operating system. The actual configura- tion is the Project MAC, MATHLAB PDP-10 computer at M.I.T. This memo presents instructions, and examples, for the use of this pro- gram, along with an annotated listing of the program. Any comments, criticisms or suggestions will be graciously accepted and gratefully acknowledged and should be addressed to the author. The implementation of the Todd-Coxeter algorithm represents the first step in an effort to develop a sophisticated collection of programs to aid in computations with groups. It is our hope to be releasing future memos detailing improvements and additions to this project. -4- 2. USER'S MANUAL FOR THE TODD-COXETER ALGORITHM 1. Find a free console on the MATHLAB system. Type p ! control-Z n 1 (ctrl-Z), ( Non - Printing ) 2. The system will type several lines relating to the number of users, operating system version, and other information. When it has been printed out, type j: LOGIN GROUP ~| followed by a carriage return (CR). 3. TEN50 will be awaiting commands when it types a new line with only a period on it (.) . 4. To run the Todd-Coxter program type: | R TC (CR)j 5. At this point, the user has a number of options relating to the input to the program: input may either be interactive via the teieypeor automatic via files on the disk, Similary, the output can be printed either on the teleype or onto a file on disk- The remainder of the description will assume teletype (TTY) for both input and output, 6. The program now prints out the following question: INPUT ON DSK (20) OR TTY (05) ? 7. Since we desire TTY as input source, we type [05 rcRjl 8. The question is now printed: OUTPUT TO DSK (21) OR TTY (05) ? 9. Again, for TTY output we type J05 (CR] 10. The program now types out the following message: TODD-COXETER ALGORITHM running on file: TTY. DAT putting, output on file: TTY. DAT 11. The program now prints out NEW PROBLEM INPUT -5- 12. At this point, the program is expecting a control number to direct its actions. To begin a new problem (i.e., a group and a subgroup), type 13. 14. TcrTI The program will now respond: PROBLEM n GROUP RELATORS where n is the current problem number* At this point, the group relators are input, using the following scheme: For each relator, one line of numbers is input. Each relator is numerically represented by a sequence of two digit numbers in the form: e.x x x (CR) 112 n 15. where e. is a positive two digit number signifying the multiplicity of the relator x. is non-zero integer representing either a generator of the group (x. positive) or the inverse of a generator of the group (x. negative) . E.g. , if a relator is «1 -2 3 (aba b ) = 1 then it is entered as the following string: 030102-1-2-2 (CR) After each line is entered the program will verify the input by printing (as in the example above) a EXP 3 1 2 -1 -2 -2 16. Enter as many lines as there are group relators. To inform the program that all the relators have been input, enter r-2 (CR)1 ■6- 17, The following line will now be typed: SUBGROUP GENERATORS 18- You now enter, in the same format as described above, the generators of the desired subgroup; again, one line of input per generator, 19. All the generators have been input, enter a This will inform the program that all the input information has been given, and also that program execution should start. (Note: if the identity subgroup is the desired input you need only type -3 when subgroup generators are asked for). 20. The Todd-Coxeter algorithm is now being applied to the input data. The program will now terminate in one of two ways: Successful Termination : In this case, the index has been determined and the following is printed: I NDEX= i MAX= m TO TAT> t Here, i will be the index, m will denote the maximum number of cosets existing at any one time during the execution, and t is the total number of cosets created. Unsuccessful Termination : In this case, the core storage was not sufficient to accomodate the computation necessary to complete the problem. L00KAHEAD UNABLE TO CONTINUE 21. In both cases, the program again types out NEW PROBLEM INPUT 22. At this point, the user may wish to proceed in one of four ways: 1) Input a new problem: enter }j-I (cr)j and proceed to step 13. 2) Terminate the session: enter 1-9 (CR)J and proceed to step 2: 3) Maintain the same group as j ust previously input but input a new subgroup :^' enter -4 (CRn and proceed to step 17, 4) Maintain the session, W_ ™ th new I/O configuration: enter _ [~-8 (CR)| and proceed to step §» 23. At the end of the session, the system types out certain run- time statistics, then types 24. EXIT tc To log off t he system, type j|7cntrl-Z)l and then r?T 5gou"t I (CR) 3 . Sample Session Number 1 U 10556) .SLEEP 17, SOu ET.'T'rS 811 CONSOLE 7 FREE. 16:46:22 EL ITS. 811. DDT. 51 6- 11. USEES ■ETERIEEDTAL SYSTEE WITH DYRAEOD MAGTAPE RCUTIGRS,ETC LED CAUTION, ANP DOET RELOAD OLD SYSTEM V.TTROUT E^EIi^G k,:,. —rr Po-Pn rrouv, j. i> i. j. *:TEE50 E.PUT Or. DSK (20) 01: TTY (05) OUTIUT TO DSK (21) OR TTY (05) ? TODD-COXETER ALGORITHM EUEKIEG OR RILE: TTY .DAT PUTTING OUTPUT OR PILE: TTY .DAT IRE-; PEOPLED IRPIT' -1 -'■•'-n-T T v ' i GROUP RELATORS a 9 1 OL =. H <XP 9 *» 8 2 1 2-1-2 A.bflL J b"'c I EXP 1 -2 -1 -2 SUBGROUP GEXEEATOR JELEX= '('/ h;-,X= \2: T01AL= AW NEE PEOELEX II3PUT _c EXECUTION TIME: 4.06 SEC. TOTAL ELAPSED TIRE: ., #,_-,^ ^-' C ' TO EXECUIICE EXPOSE ii^:i'A,iii. EXIT -10- 4. Disk Files for Input and /or Output The current implementation of the Todd-Coxeter algorithm provides a number of input-output media. In particular, the teletype (TTY) has been used for both input and output in the sample session. This section will be concerned with the use of disk files for both input and output. Naming Conventions Disk files used for the FORTRAN I/O must agree with the following rules: 1) Each file name is of the form Name- ex t 2) Name must be a 5 character word 3) Ext must be the 3 characters DAT 4) For standard (i.e. default) names are: INPUT: F0R2O.DAT OUTPUT: F0R21.DAT The user is permitted to use standard file names or provide specific I/O file names. Disk Files for Input The structure of these files mirror exactly the inputs as given in the algorithm. A sample session with disk input from file NEWCN. DAT and output to TTY is given below, along with listing of NEWCN. DAT. -11- 5 . Sample Session Number 2 EMUI 01; DSK (20) OR TTY (05) ? 20 GTAKDAED FILE BAKE (20) OR LOT (22) ? 22 ALTER 5 LETTER JTLE NAME BE WCA\ AXE OUII-UT 10 DSK (21) OR TTY (05) ? 05 T0BB-C0XETER ALGORITHM KUNNIIJG OR TILE: KERUERDA: TUTTIRG OUTPUT OR PILE: TTY .DAT **-x-* ************************** PROBLEM 2 GROUP RELATORS JL.Ai."' 8 1 iE-Ax' 7 2 F;XP 2 i 2 E,aE ./ _-i O ou I'O itOUiv Or.:i:r.iLHj. Oiuj EXP 2 EXT 1 -12 INDEX= 448 MAX= 2176 T0TAL= ****************************** ■12- PROBLEM 3 GROUP RELATORS EXP 4 3 EXP 5 2 EXP 1 2 2 - EXP 2 2 3 EXP 1 1 1 EXP 3 1 2 EXP 11 1 EXP SUBC ROUP 1 OEKEE/ 1 \TGRS 1 1-2-1 I 1 j> 3 EXP 1 1 OVERFLOW MAX= 2740 TOTAL= 3U95 720 COSETS REMAIN AFTER LOOKAKEAD INDF:X= 720 MAX= 2740 TOTAL= 35S5 PROPLEH 4 GROUP RELATORS EXP 3 1 EXP 2 1 2 EXP 2 2 ■z -> EXP 2 3 1 EXP 2 1 2 EX? 7 2 EXP 13 SUBGROUP 3 GENERA TO ?s •13- oveeflow max= 2744 tctat- 3710 20c5 cosets remain after lookahead ovfmflow max= 2744 total- 4477 25^7 cosets remain after lookahead overflow kax= 2744 iotal=- 4704 2675 cosets remah: aftfe lookahead overflow max= 2744 total- 4776 10^2 cosets rei-ain after lookahead irdrx= 1092 max= 2744 tctat- 4776 PEOPLES 5 GROUP REJATORS EXP 3 EXP •^ > EXP 3 EXP 3 O v, EXP 4 1 3 1 -3 -;-■■■ vn 4 EXP 4 f.;xf 1 EXP 5 -2 3 1-2 1 2-3 1 3 1 -3 1 2 EXP 5 -1 2 SUBGROUP GENERATORS EXP 1 EXP 1 OVERFLOW HAX= 2739 TOTAL- 3394 2287 COSETS REMAIN AFTER LOOKAHEAD OVERFLOW MAX= 2739 TOTAL= 3S : 48 2539 COSETS REMAIN AFTER LOOKAHEAD ■14- OVERFLOW MAX= 2739 TOTAIj= 4052 2702 COSETS REMAIN AFTER LOOK AHEAD OVERFLOW MAX= 2739 TOTAL= 4089 2726 COSETS REKAIN AFTER LCOKAHEAD OVFRFIOU MAX= 2739 TOTAL= 4102 2722 COSETS REKAITi AFTER LCOKAHEAD OVEEFIOlv HAX= 2739 TOTAL= 41 1S 2738 COSETS REIAIK AFTER LCOKAHEAD OVERFLOW MAX= 2739 TOTAL= 4120 2739 COSETS EEEAIN AFTER LGOKAIFAD LCOKAHEAD UNABLE TO CONTINUE ■15- ■ Tnj: 2E7C2.LA2 -1 r ■ O I 7 2 2 1 2 7-1 2 2 1 1-1 2 -1 3 - ■A -l -^ -' "1 -A 11 1 1 rf-:: t t_ 7 2 y <- c _j 4 i-o 7-1 7 1 7 1- 1 1 : 8 ■16- Disk Files for Output The structure of these files mirrors exactly the output as would be obtained using the TTY for output. In this made, however, summary information is output to the TTY. A sample session with input from file NEW CN.DAT and output to file OUTCN.DAT is given below, as well as the type - out of OUT CN.DAT. •17- 6. Sample Session Number 3 4237) .10! 1,16 $$u ML ITS 811 CONSOLE 7 FREE. 17:01:31 ML ITS. 811. DDT. 51 6. 12. USERS THE 110 BAUD NUMBER IS 258-7894. SORRY ABOUT THE MIX UP — PJ tlo/rin group INIT *:TEN .R TC INPUT Oli DSK (20) OR TTY (05) ? 2CJ, STANDARD FILE NAME (20) OR NOT (22) ? 22 ENTER 5 LETTER 1ILE NAME liEWCN OUTPUT TO DSK (21) OR TTY (05) ? STANDARD PILE NAME (21) OR NOT (23) ? 23 ENTER 5 LETTER FILE NAME OUTCN TODD-COXETER ALGORITHM RUNNING ON FILE: NEWCN.DAT PUITING OUTPUT 1 ON FILE: OUTCN.DAT ****■*-************************* PROBLEM 1 INDEX= 448 MAX= 2176 ****************************** PROBLEM 2 TOTAI- 2626 INDEX= 720 MAX= 2740 ****************************** PROBLEM 3 TOTAL= 3995 INDEX= 1092 MAX= 2744 **************** ************** TOTAL= 4776 ■18- PROBLEM 4 LOOKAHEAD UNABLE TO CONTINUE IliPUT OK DSK (20) OR TTY (05) ? TY OUTCN.DAT ***.************ *************** pROBBEi; 1 GROUP RELATORS EXP C 1 EXP 7 2 EXP 2 1 2 EXP 3 -1 2 SUBGROUP GENERATORS EXP 2 1 -1 2 INDEX= 448 KAX= 2176 *^*************************** PROBLEM 2 TOTAL= 2626 GROUP RELATORS EXP 4 EXP 5 2 EXP 1 2 2 -3 -2 3 EXP 2 2 3 3 EXP 1 1 1 1 1 -2 -1 2 EXP 3 1 2 3 EXP 11 1 ■19- SEHPR05P GENERATORS 1 1 3 EXP 1 1 OVERFLOW MAX= 2740 TOTAL= 3995 720 COSETS REMAIN AFTER LOOK AHEAD INDEX= 720 MAX= 2740 TOTAI- 3995 PROBLEM 3 GROUP RELATORS VYT 3 1 LVP 2 1 2 EXP 2 2 "a > EXF 2 3 1 EXP 2 1 2 3 EXP 7 2 EXF 13 SUBGROUP 3 GENERATORS OVERFLOW MAX= 2744 TOTAL= 3710 2065 COSETS REMAIN AFTER LOOKAHEAD OVERFLOW MAX= 2744 TOTAL= 4477 2527 COSETS REMAIN AFTER LOQKAHEAD OVERFLOW RAX= 2744 TOTAL= 4704 2675 COSETS REMAIN AFTER LOOKAHEAD OVERFLOW MAX= 2744 TOTAL= 4776 1092 COSETS REMAIN AFTER LOOKAHEAD INBEX= 1092 MAX= 2744 TOTAL= 4776 it***-*********-***************** -20- PRGBLEK 4 GROUP IJiLATORS AjI-Aj i i"w' : - i' W-* -'< i';l'-i !: ^ w V i J -X- .: a.,'W -2L >2 CCi.ll ;.'T r < ALCA' a?-;aa; afte;: .A. \V_ AT 20 T.U.r.Aii-^AD Li-jAi-.J.. 1 .!. J 'i o.l: -22- 7. MISCELLANEOUS INFORMATION Typing Errors 1. Before carriage return 2. Use "RUBOUT" or "DELETE" Keys 3. Will echo the deleted character 4. May be used in succession to delete several char. Program Interrupt : 1. Type control -C (f c) once 2. Until EXIT ft appears To continue after t C interrupt : 1. Type CONT 2. Back to same spot! To Restart 1. Type START at monitor level 2. Continue as normal Current Limitations 1. Number of generators ^ 9. 2. Number of terms in generators or relation words ^ 40, -23- 8. Getting onto the MATHLAB Computer In order to run the Todd-Coxeter Algorithm on a given problem, one must first gain access to the MATHLAB computer located at M.I.T. There are three ways of doing so: 1) If you are at M.I.T. and have access to a free ML console, simply follow the instructions in Section 2 of this memo. 2) If you are not at M.I.T., but have access to a computer on the ARPA network of computers, then you can ur 2 the MATHLAB computer by accessing it over the network. Consult your local expert on the ARPA network to find out how to do this. 3) You can access the MATHLAB computer using a terminal (teletype or Memorex) by telephone, If you have an acoustic coupler or a Dataphone. The telephone numbers are: available from Dr. Vera Pless or Richard Bonnea^, telephone number (617) 253-6026. -24- BIBLIOGRAPHY [1] Gannon, et al., "Implementation and Analysis of the Todd-Coxeter Al- gorithm", to appear in Math. Comp . [2] Coxeter & Todd, "A Practical Method for Enumerating Gosets of a Finite Abstract Group", Proc. Edinburgh Math. Soc , (2), 5(1936), 26-74. [3] J. Leech, "Coset Enumeration on Digital Computations", Proc Comb. Phil. Soc , 59(1963), 257-267. [4] H. Trotter, "A Machine Program for Coset Enumeration", Canadian Math. Bull. Vol. 7, No. 3, July 1964, pp. 357-368. [5] Grover, et al . , "Applications of Coset Enumeration", 2nd Symposium on Symbolic and Algebraic Manipulation , ACM, March 1971, pp. 183-187. [6] J. Cannon and G. Hovas , "Applications of the Todd-Coxeter Algorithm", Technical Report No. 9, Computer Aided Mathematics Project, Department of Pure Mathematics, University of Sydney, Sydney, Australia, June 1973. MIT/LCS/TM-35 AN INTERACTIVE IMPLEMENTATION OFTHE TODD-COXETER ALGORITHM Richard J. Bonneau December 1973 MASSACHUSETTS INSTITUTE OF TECHNOLOGY PROJECT MAC Reply to: Projecf MAC 545 Technology Square Cambridge, Mass. 02139 Telephone: 3 ~5 856 PUBLICATIONS TR/TM FORM TITLE OF THESIS OR REPORT: An Interactive Implementation of the Todd-Coxeter Algorithm AUTHOR(S) Richard J. Bonneau NO. ASSIGNED: MAC TM-35 Do you recommend it be made into a Project MAC technical report? If so, what type? Technical Report (formal, widely distributed) _x Technical Memo (informal, limited distribution) Do not print as a MAC publication i i i ■ f ? /// \ — . ? ? (/ .* A: r j Signature of M^C Group Leader ^ *^3r 5 , 1 °t 7 X Date PUBLICATIONS DISTRIBUTION PROJECT MAC, ROOM 417-A MASSACHUSETTS INSTITUTE OF TECHNOLOGY 545 TECHNOLOGY SQUARE CAMBRIDGE, MASS. 0213 9 December 1973 We have recently issued Project MAC Technical Memorandum TM-35: An Interactive Implementation of the Todd-Coxeter Algorithm Richard J. Bonneau AD 770-565 ABSTRACT The Todd-Coxeter Algorithm provides a systematic approach to the enumeration of cosets of a finitely presented group. This memo describes an interactive implementation of algorithm, including a manual on its use, examples, and methods of accessing the program. Applications of this algorithm are also discussed.